package com.cty.seventeenthDay;

/*
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 * */
public class Q_23 {
    public static void main(String[] args) {
        ListNode2 listNode1 = new ListNode2(1);
        ListNode2 listNode2 = new ListNode2(2);
        ListNode2 listNode3 = new ListNode2(3);
        ListNode2 listNode4 = new ListNode2(4);
        ListNode2 listNode5 = new ListNode2(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode2 listNode21 = reverseList(listNode1);
    }

    // 力扣官方题解 方法一:迭代
    /*
    * 思路:
    *   让第一个节点指向null 就行了
    *   之后的节点来回的更替
    *   时间复杂度O(n) 空间复杂度O(1)
    * */
    public static ListNode2 reverseList(ListNode2 head) {
        ListNode2 pre = null;
        ListNode2 current = head;
        while (current != null) {
            ListNode2 next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return pre;
    }
    // 力扣官方题解 方法二:递归
    /*
    * 递归到 最后一个节点n(K + 1)
    *   前一个节点 修改 n(k).next.next = n(k)
    *   返回n(k + 1) (作用 返回保存最终结果)
    *   注意:第一个节点反转后要指向null
    * */
    public static ListNode2 reverseList2(ListNode2 head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode2 newHead = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

}

class ListNode2 {
    int val;
    ListNode2 next;

    ListNode2() {
    }

    ListNode2(int val) {
        this.val = val;
    }

    ListNode2(int val, ListNode2 next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode2{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
